// -*- coding: utf-8 -*- 

package com.LeetCodeT.Greedy;

/**
 * Project: AlgorithmsLearn
 *
 * @author : yanking
 * Create time: 2022-03-03 12:39
 * IDE: IntelliJ IDEA
 * Introduction:
 */
@SuppressWarnings("AlibabaUndefineMagicConstant")
public class DiStringMatch {
    public int[] diStringMatch(String s) {
        // 根据给定的字符串队列实现对数组的排序
        int n = s.length();
        int[] ans = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            ans[i] = i;
        }
        for (int i = 0; i < n; i++) {
            check(ans, s, i);
        }
        return ans;
    }

    private void check(int[] ans, String s, int i) {
        if (i == -1) return;
        char c = s.charAt(i);
        if (c == 'I' && ans[i] > ans[i + 1]) {
            swap(ans, i, i + 1);
            check(ans, s, i - 1);
        } else if (c == 'D' && ans[i] < ans[i + 1]) {
            swap(ans, i, i + 1);
            check(ans, s, i - 1);
        }
    }

    private void swap(int[] ans, int i, int j) {
        int temp = ans[i];
        ans[i] = ans[j];
        ans[j] = temp;
        // 需要判断前面的数值是否会被影响
    }
}
